#include "AvlTree.h"
#include "SplayTree.h"
#include <vector>
#include <ctime>
#include <random>
using namespace std;

template <typename Comparable>
void AVL_BST(vector<Comparable> &data)
{
    AvlTree<Comparable> tree;
    for (int i = 0; i < data.size(); i++)
    {
        tree.insert(data[i]);
    }
    cout << "输出为： ";
    tree.printTree();
}

template <typename Comparable>
void Spl_BST(vector<Comparable> &data)
{
    SplayTree<Comparable> Tree;
    for (int i = 0; i < data.size(); i++)
    {
        Tree.insert(data[i]);
    }
    cout << "输出为： ";
    Tree.printTree();
}

template <typename Comparable>
void generator(vector<Comparable> &data, int length, int type)
{
    if (type == 1)
        for (int i = 0; i < length; i++)
        {
            data[i] = length + i;
        }
    else if (type == 0)
        for (int i = 0; i < length; i++)
        {
            data[i] = 2 * length - i;
        }
    else
    {
        for (int i = 0; i < length; i++)
        {
            data[i] = length + i;
        }
        for (int i = 0; i < length; i++)
        {
            int a = rand() % length;
            int b = rand() % length;
            Comparable digit;
            digit = data[b];
            data[b] = data[a];
            data[a] = digit;
        } ///随机打乱
    }
}

int main(void)
{
    int n;

    int ty;
    int time = 0;
    clock_t begin, end;

    std::cout << "请输入测试BST函数的向量长度：" << endl;
    std::cin >> n;

    std::cout << "请输入测试向量生成的方式（1为升序，0为降序,2为乱序（随机））：" << endl;
    std::cin >> ty;

    vector<int> vec(n);

    generator(vec, n, ty);

    begin = clock();
    cout<<"AVL ";
    AVL_BST(vec);
    end = clock();
    cout<<"\n";
    cout << "AVL用时为 " << int(end - begin) << endl;

    begin = clock();
    cout<<"Splay ";
    Spl_BST(vec);
    end = clock();
    cout<<"\n";
    cout << "Splay用时为 " << int(end - begin) << endl;
}
